package sit.engreal.leetcode.problems100;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/permutations/">46. 全排列</a>
 */
public class LeetCode46 {
    public List<List<Integer>> permute(int[] nums) {
        final List<List<Integer>> permutations = new ArrayList<>();
        final int n = nums.length;
        int[] p = new int[n];
        int[] q = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        for (; ; ) {
            final ArrayList<Integer> permutation = new ArrayList<>(n);
            for (int i : p) {
                permutation.add(nums[i]);
            }
            permutations.add(permutation);

            int i = 0;
            while (i < n && p[i] + i == n - 1) {
                i++;
            }
            if (i >= n) {
                break;
            }
            int k = 0;
            for (int j = i + 1; j < n; j++) {
                q[k] = p[j];
                k++;
            }
            for (int j = i; j >= 0; j--) {
                q[k] = p[j];
                k++;
            }
            int[] r = q;
            q = p;
            p = r;
        }
        return permutations;
    }

    public static void main(String[] args) {
        final LeetCode46 demo = new LeetCode46();
        demo.permute(new int[]{1, 2})
                .forEach(System.out::println);

        demo.permute(new int[]{1, 2, 3})
                .forEach(System.out::println);
    }
}
